package acm.浙大新生赛;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class E {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int[] arr = new int[sc.nextInt()];
        int rest=sc.nextInt();
        int k=sc.nextInt();
        int x=sc.nextInt();
        for (int i = 0; i < arr.length; i++) {
            arr[i]=sc.nextInt();
        }
//        System.out.println(fun(arr, arr.length-1, rest, k, x));
        System.out.println(dpFun(arr, arr.length, rest, k, x));
    }
    static {
        int count=10000;
        Random random=new Random();
        while (count-- > 0) {
            int n=random.nextInt(20)+1;
            int[] arr=new int[n];
            int m=random.nextInt(50)+1;
            int k=random.nextInt(20)+1;
            int x=random.nextInt(50)+1;
            for (int i = 0; i < arr.length; i++) {
                arr[i]=random.nextInt(50)+1;
            }
            int fun = fun(arr, n - 1, m, k, x);
            int dpFun = dpFun(arr, n, m, k, x);
            if (dpFun!=fun){
                System.out.println("m:"+m+"\t k:"+k+"\t x:"+x);
                System.out.println(Arrays.toString(arr));
                System.out.println("预期："+dpFun+"\t实际："+fun);
            }
        }
    }

    /**
     * 每个位置有三种情况，单删，多删，不删
     */
    public static int fun(int[] arr,int index,int rest,int k,int x){
        if (rest==0){
            return 0;
        }
        if (rest<0){
            return -1;
        }
        if (index<0){
            return 0;
        }
        int max=0;
        max=Math.max(max,fun(arr,index-1,rest-arr[index],k,x)+1); //单删
        if (index-k+1>=0&&rest-x>=0){
            max=Math.max(max,fun(arr,index-k,rest-x,k,x)+k);   //多删
        }
        max=Math.max(max,fun(arr,index-1,rest,k,x));    //不删
        return max;
    }
    public static int dpFun(int[] arr,int n,int rest,int k,int x){
        int[][] dp=new int[rest+1][arr.length+1];
        for (int r = 1; r <= rest; r++) {
            for (int i = 1; i <= n; i++) {
                dp[r][i]= (r-arr[i-1]>=0?dp[r-arr[i-1]][i-1]+1:0);
                dp[r][i]= r-x>=0&&i-k>=0? Math.max(dp[r][i], dp[r - x][i - k] + k) :dp[r][i];
                dp[r][i]=  Math.max(dp[r][i],dp[r][i-1]);
            }
        }
        return dp[rest][n];
    }
//    public
}
